package com.yohann.algorithm;

import java.io.PrintWriter;
import java.util.Arrays;

/**
 * <p>
 * 基数排序
 * </p>
 *
 * @author Yohann
 * @since 2020/12/30 13:12
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 基数排序
     *
     * @param arr 待排序数组
     */
    private static void radixSort(int[] arr) {
        //定义二维数组作为桶
        int[][] bucket = new int[10][arr.length];

        //桶顶指针
        int[] bucketPointer = new int[10];

        //分数标记
        int flag = 1;

        //计算次数
        int temp = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (temp < arr[i]) {
                temp = arr[i];
            }
        }
        int times = (temp + "").length();

        while (times > 0) {
            //指针置零
            for (int i = 0; i < bucketPointer.length; i++) {
                bucketPointer[i] = 0;
            }

            //将数据放入桶中
            for (int item : arr) {
                int element = item / flag % 10;
                bucket[element][bucketPointer[element]] = item;
                bucketPointer[element]++;
            }

            //桶中数据放回原数组
            int index = 0;
            for (int i = 0; i < bucketPointer.length; i++) {
                //如果指针不等于0 则表示桶中有数据
                if (bucketPointer[i] != 0) {
                    //该桶中数据放回原数组
                    for (int j = 0; j < bucketPointer[i]; j++) {
                        arr[index] = bucket[i][j];
                        index++;
                    }
                }
            }
            flag *= 10;
            times--;
        }
    }
}